package org.usmile.algorithms.leetcode.hard;

/**
 * 剑指 Offer 51. 数组中的逆序对
 * <p>
 * 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
 * <p>
 * 示例 1:
 * <p>
 * 输入: [7,5,6,4]
 * 输出: 5
 * <p>
 * 限制：
 * <p>
 * 0 <= 数组长度 <= 50000
 */
public class Offer_051 {
    public static void main(String[] args) {
        int[] nums = new int[] {7,5,6,4};
        System.out.println(new Offer_051_Solution().reversePairs(nums));
    }
}


class Offer_051_Solution {
    private int pairs;

    public int reversePairs(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return 0;
        }

        pairs = 0;
        mergeSort(nums, 0, nums.length - 1);

        return pairs;
    }

    private void mergeSort(int[] nums, int left, int right) {
        if (left == right) {
            return;
        }

        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);

        merge(nums, left, mid, right);
    }

    private void merge(int[] nums, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left;
        int j = mid + 1;
        int k = 0;
        while (k < temp.length) {
            if (i == mid + 1) {
                temp[k++] = nums[j++];
            } else if (j == right + 1) {
                temp[k++] = nums[i++];
            } else if (nums[i] > nums[j]) {
                pairs += (mid - i) + 1;
                temp[k++] = nums[j++];
            } else {
                temp[k++] = nums[i++];
            }
        }

        for ( k = 0; k < temp.length; k ++) {
            nums[left++] = temp[k];
        }
    }
}